package sort;

import java.util.*;

public class Quicksort {
    static Random rnd = new Random();

    public static void quickSort(int[] a, int low, int high) {
        if (low >= high)
            return;
        int separator = a[low + rnd.nextInt(high - low + 1)];
        int i = low;
        int j = high;
        while (i <= j) {
            while (a[i] < separator) ++i;
            while (a[j] > separator) --j;
            if (i <= j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
                ++i;
                --j;
            }
        }
        quickSort(a, low, j);
        quickSort(a, i, high);
    }

    // test
    public static void main(String[] args) {
        int n = 10_000_000;
        int[] a1 = rnd.ints(n).toArray();

        int[] a2 = a1.clone();
        Arrays.sort(a2);

        long time = System.currentTimeMillis();
        quickSort(a1, 0, a1.length - 1);
        System.out.println(System.currentTimeMillis() - time);

        if (!Arrays.equals(a1, a2))
            throw new RuntimeException();
    }
}
